package com.data.basic.chapter08;



import java.util.*;

/**
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

 例如，

 给定数组 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]。

 注意：

 你可以假设给定的 k 总是合理的，1 ≤ k ≤ 数组中不相同的元素的个数。
 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小
 */
public class LeetCode347 {

    private class  Freq implements Comparable<Freq>{
        // e表示元素
        //  freq:表示频次
       public int e, freq;

        public Freq(int key, Integer integer) {
            this.e = key;
            this.freq = integer;
        }

        // 频次小，优先级高
        public int compareTo(Freq other) {
            if (freq<other.freq){
                return 1;
            }else if (freq==other.freq){
                return 0;
            }
            return -1;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        // 单词计数
        TreeMap<Integer,Integer> map = new TreeMap<Integer, Integer>();

        for (int num:nums){
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }
            else {
                map.put(num,1);
            }

        }

        ProporityQueue<Freq> pq = new ProporityQueue<Freq>();
        for(int key:map.keySet()){
            if (pq.getSize()<k){
                pq.enqueue(new Freq(key,map.get(key)));
            }else if (map.get(key)>pq.getFront().freq){
                pq.dequeue();
                pq.enqueue(new Freq(key,map.get(key)));

            }
        }
        LinkedList<Integer> res = new LinkedList<Integer>();
        while (!pq.isEmpty()){
            res.add(pq.dequeue().freq);
        }
        return res;

    }




    /**
     * 二次封装的数组
     */
     class Array<E> {
        private E [] data;
        private int size;

        /**
         * 构造函数，传入
         */

        public Array(int capacity) {
            data  = (E[]) new Object[capacity];
            size=0;
        }
        // 无参数的构造函数
        public Array() {
            this(10);
        }
        // 根据数组生成新的数组
        public Array(E[] arr) {
            data = (E[]) new Object[arr.length];
            for (int i=0;i<arr.length;i++){
                data[i] = arr[i];
            }
            size = arr.length;

        }

        public int getSize() {
            return size;
        }

        public int getCapacity(){
            return data.length;
        }
        //数组是否为空
        public boolean isEmpty() {
//        return size>0?false:true ;
            return size==0 ;
        }

        /**
         * 在数组后端添加一个元素
         * @param e
         */
        public void addLast(E e){
            this.add(size,e);

        }
        public void addFirst(E e){
            this.add(0,e);

        }

        /**
         * 指定位置添加元素
         * @param index
         * @param e
         */
        public void add(int index,E e){
            if (size==data.length){//数组扩容
                resize(data.length<<1);
            }
            judgeIndex(index);

            for (int i=size-1;i>=index;i--){
                data[i+1] = data[i];
            }
            data[index] = e;
            size++;
        }

        private E[] resize(int newCapacity) {
            /**
             * 扩容数组
             */
            data = Arrays.copyOf(data,newCapacity);
            return data;
        }

        /**
         * 获取数组元素
         * @param index
         * @return
         */
        public E  get(int index){
            judgeIndex(index);
            return data[index];
        }

        /**
         * 修改元素
         * @param index
         * @param e
         */
        public void  set(int index,E e ){
            judgeIndex(index);
            data[index]=e;
        }

        /**
         *  查看是否有
         * @param e
         * @return
         */
        public boolean contains(E e){
            for(int i=0;i<size;i++){
                if (data[i].equals(e)){
                    return true;
                }
            }
            return false;
        }

        /**
         * 查找元素的下标
         * @param e
         * @return
         */
        public int find(E e){
            for(int i=0;i<size;i++){
                if (data[i].equals(e)){
                    return i;
                }
            }
            return -1;
        }

        public E getLast(){
            return get(size-1);
//        return data[size-1];  //size为0时会不合法
        }

        public E getFirst(){
            return data[0];
        }

        /**
         *  按照索引删除
         * @param index
         * @return
         */
        public E remove(int index){
            judgeIndex(index);
            E ret = data[index];
            for (int i=index+1;i<size;i++){
                data[i-1] = data[i];
            }
            // 引用置成null
            data[size]=null;
            size--;
//当数组的空间删除到够小的时候，那就减少数组的空间
            if (size<data.length>>2&&data.length!=1){
                resize(data.length>>1);
            }


            return ret;

        }

        public E removeFirst(){
            return remove(0);
        }
        public E removelast(){
            return remove(size-1);
        }

        // 判断数组下标
        private void judgeIndex(int index){
            if (index<0||index>size){
                throw new IllegalArgumentException("Get fail! index is outOfMemory");
            }
        }
        // 按照元素删除    只删除一个e
        public void removeElement(E e){
            int index = find(e);
            if (index!=-1){
                remove(index);
            }
        }

        /**
         * 交换元素
         * @return
         */
        public void swap(int i,int j){
            if (i<0||i>=size||j<0||j>=size){
                throw new IllegalArgumentException("index is illegal");
            }
            E temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }

        @Override
        public String toString() {
            StringBuffer res = new StringBuffer();
            res.append(String.format("Array:size = %d, capcity = %d\n",size,getCapacity()));
            res.append("[");
            for (int i=0;i<size;i++){
                if (i!=size){
                    res.append(data[i]);
                    res.append(",");
                }
            }
            res.append("]");
            return res.toString();
        }

    }


    /** 用自定义的数组实现完全二叉树（最大堆）的存储
     * 最大堆的定义：
     * Created by wangbing on 2018/5/21.
     */
     class MaxHeap<E extends Comparable> {

        Array<E> data;

        public MaxHeap (int capacity){
            data = new Array<E>(capacity);

        }

        /**
         * heapify的过程
         * @param arr
         */
        public MaxHeap(E[] arr){
            data = new Array<E>(arr);
            for (int i=parent(arr.length-1);i>=0;i--){
                siftDown(i);
            }
        }

        public MaxHeap() {
            data = new Array<E>();
        }


        // 返回堆中的元素
        public int size(){
            return data.getSize();
        }

        // 返回一个布尔值，表示堆是否为空
        public boolean isEmpty(){
            return data.isEmpty();
        }

        // 返回完全二叉树的数组表示，一个索引所表示元素的父亲节点的索引
        private int parent(int index){
            if (index == 0) {

                throw new IllegalArgumentException("index-0  doesn't have parent!");
            }
            return (index-1)/2;
        }

        // 返回完全二叉树的数组表示，一个索引所表示元素的左孩子节点的索引
        private int leftChild(int index){
//        if (index==(data.getSize()-1)){
//            throw new IllegalArgumentException("index-last  doesn't have left child!");
//        }
            return index*2+1;
        }
        // 返回完全二叉树的数组表示，一个索引所表示元素的右孩子节点的索引
        private int rightChild(int index){
//        if (index==(data.getSize()-1)){
//            throw new IllegalArgumentException("index-last  doesn't have right child!");
//        }
            return index*2+2;
        }


        /**
         * 向堆中添加元素
         */
        public void add(E e){
            data.addLast(e);
            siftUp(data.getSize()-1);
        }

        private void siftUp(int k) {
            while(k>0&&data.get(parent(k)).compareTo(data.get(k))<0){
                data.swap(k,parent(k));
                // 更新需要对比的数组下标
                k = parent(k);
            }
        }
        /**
         * 查看堆中最大元素
         */
        public E findMax(){
            if (data.getSize()==0){
                throw new IllegalArgumentException("cannot find max   when heap is empty!");

            }
            return data.get(0);
        }

        /**
         * 从堆中删除元素
         */
        public E extractMax(){
            E ret = findMax();
            // 完成元素的交换
            data.swap(0,data.getSize()-1);
            data.removelast();
            // 最大堆的调整

            siftDown(0);


            return ret;
        }

        private void siftDown(int k) {


            // 当左孩子的索引越界了，就停止；因为右孩子对应的数组下标大于左孩子的数组下标
            while (leftChild(k)<data.getSize()){

                int j = leftChild(k);
                if (j+1<data.getSize() && data.get(j+1).compareTo(data.get(j))>0){
                    // 此时data[j] 是left child和right child中最大值
                    // 或者j++
                    j = rightChild(k);


                }
                if (data.get(k).compareTo(data.get(j))>=0){
                    break;

                }
                data.swap(k,j);
                k = j;



            }

        }


        /**
         * 取出堆中的最大元素
         */
        public E replace(E e){
            E ret = findMax();
            data.set(0,e);
            siftDown(0);
            return ret;

        }

    }


    /**   优先队列的实现：利用最大堆来实现优先队列
     * Created by wangbing on 2018/5/31.
     */
    public interface Queue<E> {
        // 入队
        void enqueue(E e);
        // 出队
        E dequeue();
        //    取出对头
        E getFront();
        // 队列大小
        int getSize();
        // 是否为空
        boolean isEmpty();

    }
     class ProporityQueue<E extends Comparable<E>> implements Queue<E> {

        private MaxHeap<E> maxHeap;

        public ProporityQueue() {
            maxHeap = new MaxHeap<E>();
        }

        public void enqueue(E e) {
            maxHeap.add(e);

        }

        public E dequeue() {
            return maxHeap.extractMax();
        }

        public E getFront() {
            return maxHeap.findMax();
        }


        public int getSize() {
            return maxHeap.size();
        }

        public boolean isEmpty() {
            return maxHeap.isEmpty();
        }
    }




}
